package commonusealgorithm;

/**
 * @Author PoX21s
 * @Date: 2021/10/30 13:44
 * @Version 1.0
 */

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1,5,7,23,111,123,422};
        int index = binarySort(arr, 1);

        System.out.println("index:" + index);

    }

    /*
    * 思路
    * - 传入原数组和目标值
    * - 找到中点，进行比较
    *   - 大于，右边二分
    *   - 小于左边二分
    * - 不断二分直到截取到的数组只有一个数字
    *   - 是则返回当前下标
    *   - 不是则返回-1，代表该数组没有目标值，无法找到
    * */
    public static int binarySort(int[] arr, int target){
        int left = 0;
        int right = arr.length-1;

        while (left <= right){
            int mid = (left + right) / 2;

            if (arr[mid] == target){
                return mid;
            } else if (target > arr[mid]){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return  -1;
    }
}
